package com.practice.misc;

public class SquareSplit {
	private int[][] dp;
	
	public int minSquares(int w, int h) {
		int a = Math.min(w, h);
		int b = Math.max(w, h);
		dp = new int[a+1][b+1];
		
		for (int i=0; i<=b; i++) {
			dp[0][i] = 0;
			dp[1][i] = i;
		}
		
		for (int i=2; i<=a; i++) {
			for (int j=0; j<=b; j++) {
				dp[i][j] = -1;
			}
		}
		return calc(a, b);
	}
	
	private int calc(int w, int h) {
		int a = Math.min(w, h);
		int b = Math.max(w, h);
		
		if (dp[a][b] >= 0) return dp[a][b];
		
		int min = Integer.MAX_VALUE;
		for (int i=1; i<=a; i++) {
			min = Math.min(min, 1 + calc(a-i, i) + calc(a, b-i));
			min = Math.min(min, 1 + calc(b-i, i) + calc(a-i, b));
		}
		
		dp[a][b] = min;
		return min;
	}
}
